翻訳と辞書 Words near each other ・ "O" Is for Outlaw ・ "O"-Jung.Ban.Hap. ・ "Ode-to-Napoleon" hexachord ・ "Oh Yeah!" Live ・ "Our Contemporary" regional art exhibition (Leningrad, 1975) ・ "P" Is for Peril ・ "Pimpernel" Smith ・ "Polish death camp" controversy ・ "Pro knigi" ("About books") ・ "Prosopa" Greek Television Awards ・ "Pussy Cats" Starring the Walkmen ・ "Q" Is for Quarry ・ "R" Is for Ricochet ・ "R" The King (2016 film) ・ "Rags" Ragland ・ ! (album) ・ ! (disambiguation) ・ !! ・ !!! ・ !!! (album) ・ !!Destroy-Oh-Boy!! ・ !Action Pact! ・ !Arriba! La Pachanga ・ !Hero ・ !Hero (album) ・ !Kung language ・ !Oka Tokat ・ !PAUS3 ・ !T.O.O.H.! ・ !Women Art Revolution Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク exact cover ： ウィキペディア英語版 exact cover In mathematics, given a collection $\backslash mathcal$ of subsets of a set ''X'', an exact cover is a subcollection $\backslash mathcal^$ * of $\backslash mathcal$ such that each element in ''X'' is contained in ''exactly one'' subset in $\backslash mathcal^$ *. One says that each element in ''X'' is covered by exactly one subset in $\backslash mathcal^$ *. An exact cover is a kind of cover. In computer science, the exact cover problem is a decision problem to determine if an exact cover exists. The exact cover problem is NP-complete〔 This book is a classic, developing the theory, then cataloguing ''many'' NP-Complete problems. 〕 and is one of Karp's 21 NP-complete problems.〔 〕 The exact cover problem is a kind of constraint satisfaction problem. An exact cover problem can be represented by an incidence matrix or a bipartite graph. Knuth's Algorithm X is an algorithm that finds all solutions to an exact cover problem. DLX is the name given to Algorithm X when it is implemented efficiently using Donald Knuth's Dancing Links technique on a computer.〔 The standard exact cover problem can be generalized slightly to involve not only "exactly one" constraints but also "at-most-one" constraints. Finding Pentomino tilings and solving Sudoku are noteworthy examples of exact cover problems. The N queens problem is a slightly generalized exact cover problem. == Formal definition == Given a collection $\backslash mathcal$ of subsets of a set ''X'', an exact cover of ''X'' is a subcollection $\backslash mathcal^$ * of $\backslash mathcal$ that satisfies two conditions: * The intersection of any two distinct subsets in $\backslash mathcal^$ * is empty, i.e., the subsets in $\backslash mathcal^$ * are pairwise disjoint. In other words, each element in ''X'' is contained in ''at most one'' subset in $\backslash mathcal^$ *. * The union of the subsets in $\backslash mathcal^$ * is ''X'', i.e., the subsets in $\backslash mathcal^$ * cover ''X''. In other words, each element in ''X'' is contained in ''at least one'' subset in $\backslash mathcal^$ *. In short, an exact cover is "exact" in the sense that each element in ''X'' is contained in ''exactly one'' subset in $\backslash mathcal^$ *. Equivalently, an exact cover of ''X'' is a subcollection $\backslash mathcal^$ * of $\backslash mathcal$ that partitions ''X''. For an exact cover of ''X'' to exist, it is necessary that: * The union of the subsets in $\backslash mathcal$ is ''X''. In other words, each element in ''X'' is contained in at least one subset in $\backslash mathcal$. If the empty set ∅ is contained in $\backslash mathcal$, then it makes no difference whether or not it is in any exact cover. Thus it is typical to assume that: * The empty set is not in $\backslash mathcal^$ *. In other words, each subset in $\backslash mathcal^$ * contains at least one element. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「exact cover」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.